package cn.orange.ch05_stack;

import java.util.LinkedList;

/**
 * LC42.接雨水
 */
public class LC42 {
    public int trapD(int[] height) { //双指针解法
        int ans = 0;
        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);
            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
    public int trap(int[] height) { //单调栈解法
        int ans = 0;
        LinkedList<Integer> stk = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
            int h = height[i];
            while (!stk.isEmpty() && h > height[stk.peek()]) {
                Integer pop = stk.pop();
                if (!stk.isEmpty()) {
                    int hi = Integer.min(h, height[stk.peek()]) - height[pop];
                    int wi = i - stk.peek() - 1;
                    ans += hi * wi;
                }
            }
            stk.push(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        LC42 alg = new LC42();
        System.out.println(alg.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(alg.trap(new int[]{4, 2, 0, 3, 2, 5}));
        System.out.println(alg.trapD(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(alg.trapD(new int[]{4, 2, 0, 3, 2, 5}));
    }
}
